package nowcoder.zuo;

/**
 * 	[题目]
 * 	给定一个有序数组arr，调整arr使得这个数组的左半部分没有重复元素且升序，
 * 	而不用保证右部分是否有序。
 * 	
 * 	[举例]
 *	arr=[1,2,2,2,3,3,4,5,6,6,7,7,8,8,8,9]
 *	调整之后arr=[1,2,3,4,5,6,7,8,9,...]
 *
 *	[补充题目]
 *	给定一个数组arr，其中只可能含有0,1,2三个值，请实现arr的排序
 *	另一种问法：有一个数组，其中只有红球、蓝球和黄球，请实现
 *		红球全放在数组的左边，蓝球放在中间，黄球放在右边。
 *	另一种问法：有一个数组，再给定一个值k，实现比k小的数
 *		都放在数组的左边，等于k的放在中间，比k大的放在右边。
 *
 *	[要求]
 *	时间O(N)，空间O(1)
 */

/**
 * @author      zxwtry
 * @email       zxwtry@qq.com
 * @project     OJ
 * @package     nowcoder.zuo
 * @file        Book109_数组的partition调整.java
 * @type        Book109_数组的partition调整
 * @date        2017年1月3日 下午9:09:03
 * @details     
 */
public class Book109_数组的partition调整 {
	static class Solution1 {
		public void partition(int[] arr) {
			if (arr == null || arr.length < 2) return;
			int u = 0, i = 1;
			while (i != arr.length) {
				if (arr[i ++] != arr[u]) {
					swap(arr, ++u, i - 1);
				}
			}
		}
		private void swap(int[] arr, int i, int j) {
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	static class Solution2 {
		public void partition(int[] arr) {
			if (arr == null || arr.length < 2) return;
			int left = -1, index = 0, right = arr.length;
			while (index < right) {
				if (arr[index] == 0) {
					swap(arr, ++ left, index ++);
				} else if (arr[index] == 2) {
					swap(arr, index, -- right);
				} else {
					index ++;
				}
			}
		}
		private void swap(int[] arr, int i, int j) {
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
}
